public class Test {
    /**
     * 动态规划算法相关解题代码*/

    /**
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int tribonacci(int n) {
        //在动态规划之前，我们需处理边界情况
        if(n==0) return 0;
        if(n==1 || n==2) return 1;

        //1 创建dp表-由于是返回第n个数，故数组长度要为n+1
        int[] dp = new int[n+1];
        //2 初始化
        dp[0] = 0; dp[1] = 1; dp[2] = 1;
        for(int i = 3; i < dp.length; i++) {
            //3 填表-状态转移方程
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        //返回值
        return dp[n];
    }

    /**
     * 优化
     * 时间复杂度O（n）
     * 空间复杂度O（1）*/
    public int tribonacciOne(int n) {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;

        int a = 0, b = 1, c = 1, ret = 0;
        for(int i = 3; i <= n; i++) {
            ret = a+b+c;
            a=b;
            b=c;
            c=ret;
        }
        return ret;
    }

    /**
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int waysToStep(int n) {
        //处理边界情况
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;

        //创建MOD为模数
        int MOD = (int)1e9 + 7;

        //创建dp表
        int[] dp = new int[n+1];
        //初始化
        dp[1] = 1; dp[2] = 2; dp[3] = 4;
        for(int i = 4; i <= n; i++) {
            //状态转移方程
            dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;
        }
        return dp[n];
    }
}
